use crate::*;

#[test]
fn test1() {
    let mut rbt = RBTree::<i32, i32>::new();
    rbt.insert(1, 1);
    rbt.insert(2, 2);
    rbt.insert(3, 3);
    rbt.insert(4, 4);
    rbt.insert(5, 5);
    rbt.insert(6, 6);
    rbt.insert(7, 7);
    rbt.insert(8, 8);
    rbt.insert(9, 9);
    for (k, v) in &rbt {
        println!("key: {}, value: {}", k, v);
    }
}

#[test]
fn test2() {
    let mut rbt = RBTree::<i32, i32>::new();
    rbt.insert(1, 1);
    rbt.insert(2, 2);
    rbt.insert(3, 3);
    rbt.insert(4, 4);
    rbt.insert(5, 5);
    rbt.insert(6, 6);
    rbt.insert(7, 7);
    rbt.insert(8, 8);
    rbt.insert(9, 9);
    println!("inorder");
    rbt.inorder();
    println!("");
    println!("modify node 8");
    rbt.modify(&8, 10);
    rbt.inorder();
    println!("");
    println!("delete node 8");
    rbt.remove(&8);
    rbt.inorder();
    println!("");
}


#[test]
fn test3() {
    let mut rbt = RBTree::<i32, i32>::new();
    rbt.insert(1, 1);
    rbt.insert(2, 2);
    rbt.insert(3, 3);
    rbt.insert(4, 4);
    rbt.insert(5, 5);
    assert_eq!(rbt.get(&3), Some(&3));
    assert!(rbt.is_balanced());
    assert_eq!(rbt.len(), 5);
    rbt.remove(&3);
    assert_eq!(rbt.len(), 4);
    assert_eq!(rbt.get(&3), None);
    assert!(rbt.is_balanced());
}

#[test]
fn test3_2() {
    let mut rbt = RBTree::<i32, i32>::new();
    for i in 0..10000 {
        rbt.insert(i, i);
    }
    assert_eq!(rbt.len(), 10000);
    assert!(rbt.is_balanced());
    for i in 0..10000 {
        assert_eq!(rbt.get(&i), Some(&i));
    }
    for i in 0..10000 {
        rbt.remove(&i);
    }
    assert_eq!(rbt.len(), 0);
    assert!(rbt.is_balanced());
    for i in 0..10000 {
        rbt.insert(i, i);
    }
    for i in 0..10000 {
        rbt.modify(&i, i + 1);
    }
    for i in 0..10000 {
        assert_eq!(rbt.get(&i), Some(&(i + 1)));
    }
}


#[test]
fn test3_3() {
    let mut rbt = RBTree::<i32, String>::new();
    for i in 0..10000 {
        rbt.insert(i, format!("value_{}", i));
    }
    assert_eq!(rbt.len(), 10000);
    assert!(rbt.is_balanced());
    for i in 0..10000 {
        assert_eq!(rbt.get(&i), Some(&format!("value_{}", i)));
    }
    for i in 0..10000 {
        rbt.remove(&i);
    }
    assert_eq!(rbt.len(), 0);
    assert!(rbt.is_balanced());
    for i in 0..10000 {
        rbt.insert(i, format!("value_{}", i));
    }
    for i in 0..10000 {
        rbt.modify(&i, format!("new_value_{}", i));
    }
    for i in 0..10000 {
        assert_eq!(rbt.get(&i), Some(&format!("new_value_{}", i)));
    }
}

#[test]
fn test4() {
    let mut rbt = RBTree::<i32, String>::new();
    
    // 插入大量数据
    for i in 0..10000 {
        rbt.insert(i, format!("value_{}", i));
    }
    assert_eq!(rbt.len(), 10000);
    // 验证树的平衡性
    assert!(rbt.is_balanced());
    
    // 随机查找和修改
    for _ in 0..1000 {
        let key = (rand::random::<u32>() % 10000) as i32;
        assert_eq!(rbt.get(&key), Some(&format!("value_{}", key)));
        //println!("key: {}, value: {:?}", key, rbt.get(&key));
    }
    for _ in 0..1000 {
        let key = (rand::random::<u32>() % 10000) as i32;
        rbt.modify(&key, format!("new_value_{}", key));
    }
    assert_eq!(rbt.len(), 10000);
    assert!(rbt.is_balanced());
    
    // 随机删除
    let mut removed_keys = Vec::new();
    for _ in 0..5000 {
        let key = (rand::random::<u32>() % 10000) as i32;
        rbt.remove(&key);
        removed_keys.push(key);
    }
    
    // 验证删除的键不存在
    // for key in &removed_keys {
    //     assert_eq!(rbt.get(key), None);
    // }
    
    // 重新插入删除的键
    // for key in removed_keys {
    //     rbt.insert(key, format!("reinserted_{}", key));
    // }
    
    // 最终验证树的平衡性和大小
    // assert!(rbt.is_balanced());
    // assert_eq!(rbt.len(), 10000);
}